#ifndef HASHSET_H
#define HASHSET_H

#include <memory.h>

/* Hash set data structure. */
#define HashSet(Ty, MaxItems, NumBuckets) \
    struct { \
        struct { \
            Ty key;                 /* key of the item */           \
            unsigned next;          /* index to next node + 1 */    \
        } items[MaxItems];          /* array of nodes */            \
        unsigned num_items;         /* number of nodes */           \
        unsigned head[NumBuckets];  /* index to first node + 1 */   \
        unsigned (*hash)(Ty);       /* hash function */             \
        int (*compare)(Ty, Ty);     /* comparison function */       \
    }

/* Initializes a hash set. */
#define HashSet_init(Set, Hasher, Comparer)         \
    do {                                            \
        (Set).compare = (Comparer);                 \
        (Set).hash = (Hasher);                      \
        (Set).num_items = 0;                        \
        memset((Set).head, 0, sizeof((Set).head));  \
    } while (0)

/* Clears the elements in the hash set. */
#define HashSet_clear(Set)                          \
    do {                                            \
        memset((Set).head, 0, sizeof((Set).head));  \
        (Set).num_items = 0;                        \
    } while (0)

/* Returns the number of buckets in a hash set. */
#define HashSet_numBuckets(Set) (sizeof((Set).head)/sizeof((Set).head[0]))

/* Compares two keys using the hash set's comparison function. */
#define HashSet_compare(Set, Key1, Key2) \
    (((Set).compare)? (Set).compare((Key1),(Key2)) : (Key1)-(Key2))

/* Computes the hash value of a key using a hash set's hash function. */
#define HashSet_hash(Set, Key) \
    (((Set).hash)? (Set).hash((Key)) : (unsigned int)(Key))

/* Looks up the hash set for a given key. If the key is found, its one-based
 * index is stored in ReturnIndex; if the key is not found, 0 is stored.
 */
#define HashSet_find(Set, Key, ReturnIndex) \
    do { \
        unsigned code = HashSet_hash(Set, Key);                         \
        unsigned bucket = code % HashSet_numBuckets(Set);               \
        unsigned k;                                                     \
        for (k = (Set).head[bucket]; k; k = (Set).items[k-1].next)      \
            if (HashSet_compare(Set, Key, (Set).items[k-1].key) == 0)   \
                break;                                                  \
        (ReturnIndex) = k;                                              \
    } while (0)

/* Adds a key into a hash set. Returns the one-based index of the added key
 * in ReturnIndex. If the key already exists in the hash set, the effect is
 * the same as HashSet_find(Set, Key, ReturnIndex). Since the key is copied
 * by bytes into the hash set, it must be an l-value of the key type.
 */
#define HashSet_add(Set, Key, ReturnIndex) \
    do { \
        unsigned code = HashSet_hash(Set, Key);                         \
        unsigned bucket = code % HashSet_numBuckets(Set);               \
        unsigned k;                                                     \
        for (k = (Set).head[bucket]; k; k = (Set).items[k-1].next)      \
            if (HashSet_compare(Set, Key, (Set).items[k-1].key) == 0)   \
                break;                                                  \
        if (k == 0) {                                                   \
            k = ++(Set).num_items;                                      \
            (Set).items[k-1].next = (Set).head[bucket];                 \
            (Set).head[bucket] = k;                                     \
            memcpy(&(Set).items[k-1].key, &(Key),                       \
                   sizeof((Set).items[0].key));                         \
        }                                                               \
        (ReturnIndex) = k;                                              \
    } while (0)

/* Returns the number of elements in a hash set. */
#define HashSet_size(Set) ((Set).num_items)

/* Gets the item key at a given one-based index. */
#define HashSet_get(Set, Index) ((Set).items[(Index)-1].key)

/* Default string hash function. */
unsigned strhash(const char *s)
{
    unsigned power = 1;
    unsigned code = 0;
    for (; *s; s++)
    {
        code += (unsigned char)(*s) * power;
        power *= 31;
    }
    return code;
}

#endif /* HASHSET_H */
